package Lee_code;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;

/**
 * @author blh
 * @date 2024年06月21日 11:20
 * LRU least recently used 最近最少使用
 */
public class LRUCache {

    private HashMap<Integer, Integer> cache;
    private Deque<Integer> deque;
    private int size;

    public LRUCache(int capacity) {
        // 哈希表来储存 K-V 键值对, 无需修改
        cache = new HashMap<>();
        // 这是用来存储key值的
        deque = new ArrayDeque<>(capacity);
        this.size = capacity;
    }

    public int get(int key) {
        if (deque.contains(key)) {
            // 更新缓存
            deque.remove(key);
            deque.offer(key);
            return cache.get(key);
        }
        return -1;
    }

    public void put(int key, int value) {

        if (this.deque.contains(key)) {
            // 更新缓存
            deque.remove(key);
            deque.offer(key);
        }
        // 队列不满, 直接添加
        else if (deque.size() < this.size) {
            deque.offer(key);
            this.cache.put(key, value);
        } else {
            this.cache.remove(this.deque.poll());
            this.deque.offer(key);
            this.cache.put(key, value);
        }
    }
}
